import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Objects;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

public class LR1SyntaxAnalyzer {
    private static List<LR1SyntaxAnalyzer.Production> productions = new ArrayList<>(); //文法产生式
    private static List<Map<String, String>> actionTable = new ArrayList<>();  //action表
    private static List<Map<String, Integer>> gotoTable = new ArrayList<>();  //goto表
    private static LinkedHashSet<String> terminals=new LinkedHashSet<>();  //全部终结符
    private static LinkedHashSet<String> nonTerminals=new LinkedHashSet<>();  //全部非终结符
    private  static Map<String, Set<String>> firstSets;  //文法的first集
    private  static Map<String, Set<String>> followSets;  //文法的follow集
    public static List<String> result = new ArrayList<>(); // 语法分析结果

    // 简化的产生式表示
    public static class Production {   //产生式类
        String left;  //左边
        List<String> right;  //右边按链表存放

        @Override
        public String toString() {
            return left +  "->" + right;
        }

        public Production(String left, List<String> right) {
            this.left = left;
            this.right = right;
        }
    }

    // 项目表示
    static class LR1Item {  //LR1项目
        Production production; //产生式
        int dotPosition;  //点的位置
        String prospect; // 展望串
        public LR1Item(Production production, int dotPosition, String prospect) {
            this.production = production;
            this.dotPosition = dotPosition;
            this.prospect = prospect;
        }

        @Override
        public String toString() {
            return production + " " + dotPosition + " " + prospect;
        } //重载输出格式

        // 使用HashSet进行去重要重载equals函数和hashCode函数
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            LR1Item lr1Item = (LR1Item) o;
            return dotPosition == lr1Item.dotPosition && Objects.equals(production, lr1Item.production) && Objects.equals(prospect, lr1Item.prospect);
        }

        @Override
        public int hashCode() {
            return Objects.hash(production, dotPosition, prospect);
        }
    }

    // 语法分析过程
    public List<String> analyze(String syntaxFilePath, List<String> tokens) {

        // 读取文法
        productions=ReadFile.readProductions(syntaxFilePath);

        // 拓广文法， 用S''避免和其他文法符号冲突
        Production newProduction = new Production("S''", new ArrayList<String>(Collections.singletonList(productions.get(0).left)));
        productions.add(0, newProduction);

        // 根据文法求非终结符和集合和终结符集合
        for(Production production:productions){  //遍历全部产生式的左边即可获得所有非终结符
            if(!nonTerminals.contains(production.left)) {
                nonTerminals.add(production.left);
            }
        }
        for(Production production:productions){  //遍历全部产生式的右边，如果符号不在非终结符中就是终结符
            for(String s:production.right){
                if(!nonTerminals.contains(s)){
                    terminals.add(s);
                }
            }
        }
        terminals.add("#");
        if (Config.showMoreInfo) {
            System.out.println("非终结符:");
            System.out.println(nonTerminals);
            System.out.println("终结符:");
            System.out.println(terminals);
        }

        // 计算first集和follow集
        firstSets = computeFirst();   //计算first集
        followSets = computeFollow(firstSets);  //根据first集计算follow集
        if (Config.showMoreInfo) {
            System.out.println("First集合：");
            for (Map.Entry<String, Set<String>> entry : firstSets.entrySet()) {
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }
            System.out.println("Follow集合：");
            for (Map.Entry<String, Set<String>> entry : followSets.entrySet()) {
                System.out.println(entry.getKey() + " : " + entry.getValue());
            }
        }

        // 构造LR(1)分析表（Action表和Goto表）
        constructLR1Tables();
        if (Config.showMoreInfo) {
            System.out.println("Action表:");
            
            List<String> strList = Collections.singletonList(actionTable.toString());
            ReadFile.writeToFile("test_output/action.txt", strList);
            // System.out.println("\nGoto表:");
            // printTable2(gotoTable);
        }

        // 将tokens序列转化成字符串输入序列
        List<String> input = transform(tokens);
        if (Config.showMoreInfo) {
            System.out.println("语法分析字符串输入序列:");
            System.out.println(input);
        }

        // 根据分析表进行语法分析
        Stack<String> symbolStack=new Stack<>();  //符号栈
        Stack<Integer> stateStack=new Stack<>();  //状态栈
        System.out.println("----- 语法分析结果 -----");
        List<String> result = parse(input,symbolStack,stateStack); //通过查表进行语法分析
        return result;
    }

    // 将tokens序列转化成字符串输入序列
    public List<String> transform(List<String> tokens) {
        List<String> tokensMid = new ArrayList<>();
        for (String token : tokens) {
            int tabIndex = token.lastIndexOf('\t');
            int leftIndex = token.lastIndexOf('<');
            int commaIndex = token.lastIndexOf(',');
            String result = token.substring(0, tabIndex);
            String type = token.substring(leftIndex + 1, commaIndex);
            if(type.equals("IDN")||type.equals("INT")||type.equals("FLOAT")||type.equals("CHAR")||type.equals("STRING")){ //将词法分析的结果转化为语法分析的输入
                if (type.equals("IDN")) {
                    tokensMid.add("Ident");
                } else {
                    tokensMid.add(type);
                }
            }
            else
                tokensMid.add(result);
        }
        return tokensMid;
    }

    // 根据分析表对输入串进行分析
    public List<String> parse(List<String> input, Stack<String> symbolStack, Stack<Integer> stateStack){
        symbolStack.clear();  //先将两个栈全部清空
        stateStack.clear();
        symbolStack.push("#");  //符号栈栈顶为#
        stateStack.push(0);  //初始状态为0
        input.add("#");  //输入串需要加入后缀#
        int index=0;  //输入串当前字符的索引
        int i=1;  //打印
        List<String> operation=new LinkedList<>();  //存储每一步对应的操作，实际访问时访问的应该是当前状态下一步应采取的措施
        operation.add("move");  //第一步一定是移进

        String resultStr = "";
        resultStr += i + "\t" + symbolStack.peek() + "#" + input.get(0) + "\t";



        while(index<input.size()){
            String currentSymbol=input.get(index);  //面临输入串的符号
            int currentState=stateStack.peek();  //当前状态
            Map<String, String> row = actionTable.get(currentState);  //在action表中先查找当前状态对应的map
            if (row.get(currentSymbol)==null) {currentSymbol = "$";index--;}  //如果当前符号在map中对应下一步的操作不存在，先考虑空串规约的情况
            if(row.get(currentSymbol)!=null){  //如果本来就不为空或者空串规约可行
                String s=actionTable.get(currentState).get(currentSymbol);  //当前状态面临符号应采取的操作
                if(s.startsWith("s")){  //移进操作
                    stateStack.push(Integer.parseInt(s.substring(1)));  //更新栈顶状态
                    symbolStack.push(currentSymbol);  //当前符号进栈
                    operation.add("move");
                    index++;
                } else if (s.startsWith("r")) {  //规约操作
                    Integer s1=Integer.parseInt(s.substring(1));
                    List<String> right=productions.get(s1-1).right;  //对应的规约所用文法
                    Integer length=right.size();
                    for(int j=0;j<length;j++){  //根据规约串的右边的长度进行出栈
                        stateStack.pop();
                        symbolStack.pop();
                    }
                    symbolStack.push(productions.get(s1-1).left);  //状态栈顶放入规约结果
                    Integer stateAfterReduction=stateStack.peek();  //取出当前状态与当前符号(因为进行了规约所以一定是非终结符)
                    String symbolAfterReduction=symbolStack.peek();
                    if(gotoTable.get(stateAfterReduction).get(symbolAfterReduction)!=null){ //查找goto表
                        stateStack.push(gotoTable.get(stateAfterReduction).get(symbolAfterReduction));  //更新当前状态
                    }
                    operation.add("reduction");
                } else if (s.equals("acc")) {  //接受，语法分析成功
                    operation.add("accept");
                    resultStr += operation.get(i);
                    result.add(resultStr);
                    break;
                }
                else{   //若不是以上三者，那么语法分析出错
                    operation.add("error");
                    resultStr += operation.get(i);
                    result.add(resultStr);
                    break;
                }
            }
            else{  //若空串规约也不可行，再去报错
                operation.add("error   row.get(currentSymbol)==null");
                resultStr += operation.get(i);
                result.add(resultStr);
                break;
            }
//            System.out.print(operation.get(i));  //要在下一步的操作进行后再打印上次打印剩余没打印的那部分，即下一步要采取的操作
//            System.out.println();
            resultStr += operation.get(i);
            result.add(resultStr);
            resultStr = "";
            i++;  //步骤更新
            resultStr += i + "\t" + symbolStack.peek() + "#" + input.get(index) + "\t";
        }
        for (String line : result) {
            System.out.println(line);
        }
        return result;
    }

    // 构造LR1分析表
    private static void constructLR1Tables() {

        // 构造项目集族
        List<Set<LR1Item>> itemSets = constructItemSets(productions);
        if (Config.showMoreInfo) {
            System.out.println("LR(1)项目集族:");
            for(Set<LR1Item> set:itemSets) {
                System.out.println(set);
            }
        }

        // 初始化Action表和Goto表
        for (int i = 0; i < itemSets.size(); i++) {
            actionTable.add(new LinkedHashMap<>());
            gotoTable.add(new LinkedHashMap<>());
        }

        // 填充Action表和Goto表
        for (int i = 0; i < itemSets.size(); i++) {
            Set<LR1Item> itemSet = itemSets.get(i);  //对于一个项目集族
            for (LR1Item item : itemSet) {
                if (item.dotPosition < item.production.right.size()) {  //对于移进项目
                    // 对于形如 A -> α·Xβ 的项目，计算 Goto(I, X) 并填入表中
                    String nextSymbol = item.production.right.get(item.dotPosition);  //找到符号
                    int nextState = gotoTable.get(i).getOrDefault(nextSymbol, -1);  //goto表接受这个非终结符后的下一个状态
                    if (nextState == -1) { //如果没有找到下一个状态，即goto表中没有保存
                        nextState = findGoto(itemSet, nextSymbol, itemSets);  //找到当前项目集族经过这个符号应该成为的下一个项目集族
                        if(nonTerminals.contains(nextSymbol)){  //非终结符就是goto表
                            gotoTable.get(i).put(nextSymbol, nextState);
                        } else if (terminals.contains(nextSymbol)) {  //终结符就是action表，前面加个s
                            actionTable.get(i).put(nextSymbol, "s" + nextState);
                        }
                    }
                } else {  //对于非移进项目
                    // 对于形如 A -> α· 的项目，计算 Action 表
                    if (item.production.left.equals(productions.get(0).left)) {
                        // 接受状态
                        actionTable.get(i).put("#", "acc");  //在这个状态中放入这个键值对
                    } else {
                        // 归约状态
                        int productionIndex = productions.indexOf(item.production);
                        actionTable.get(i).put(item.prospect, "r" + (productionIndex+1));
                        //其他为空都表示错误状态
                    }
                }
            }
        }
        
    }

    // 构造项目集
    private static List<Set<LR1Item>> constructItemSets(List<Production> productions) { //构造LR1项目集族
        List<Set<LR1Item>> itemSets = new ArrayList<>();  //全部的项目集族
        Set<LR1Item> items = new LinkedHashSet<>(Collections.singletonList(new LR1Item(productions.get(0), 0, "#"))); //取出第一个项目(eg:S'->·E, $)
        Set<LR1Item> initialItemSet = closure(items);
        itemSets.add(initialItemSet);  //加入I0
        Queue<Set<LR1Item>> queue = new LinkedList<>();
        queue.add(initialItemSet);

        while (!queue.isEmpty()) {
            Set<LR1Item> currentSet = queue.poll();  // 移除并返回队列头部的元素
            Map<String, Set<LR1Item>> gotoMap = new LinkedHashMap<>(); //创建一个空的映射 gotoMap，用于存储从当前项目集通过某个符号转移到下一个项目集的映射关系

            for (LR1Item item : currentSet) {  //遍历每个项目
                if (item.dotPosition < item.production.right.size()) {
                    String nextSymbol = item.production.right.get(item.dotPosition);  //对应位置上的符号
                    Set<LR1Item> gotoSet = gotoMap.computeIfAbsent(nextSymbol, k -> new LinkedHashSet<>());  //若有映射(即对应的项目集族)则返回这个映射，否则创建一个新的并返回
                    gotoSet.add(new LR1Item(item.production, item.dotPosition + 1, item.prospect)); //向右移动一位后的加入这个映射返回的项目集族中
                }
            }
            for (Map.Entry<String, Set<LR1Item>> entry : gotoMap.entrySet()) {  //遍历在上面的循环中项目集族所得出的所有其他的项目集族
                Set<LR1Item> gotoSet = closure(entry.getValue());  //去计算他们的闭包
                if (!itemSets.contains(gotoSet)) { //全部的项目集族中不含有这个计算完闭包后的项目集族就加入
                    itemSets.add(gotoSet);
                    queue.add(gotoSet);
                }
            }
        }
        return itemSets;
    }

    // 闭包算法
    private static Set<LR1Item> closure(Set<LR1Item> items) { //闭包
        Set<LR1Item> closure = new LinkedHashSet<>(items);  //以自身为起点
        boolean added;
        do {
            added = false;
            Set<LR1Item> newItems = new LinkedHashSet<>(closure);
            for (LR1Item item : newItems) {  //遍历每个项目
                if (item.dotPosition < item.production.right.size()) { //点不在产生式右边的最右端
                    String nextSymbol = item.production.right.get(item.dotPosition); //点的右边对应的符号
                    for (Production production : productions) {
                        if (production.left.equals(nextSymbol)) {  //遍历产生式，若某个产生式的左边是nextSymbol
                            // 对于项目α·Xβ [A->α·Bβ,a]，对FIRST(β,a)中的每一个终结符b，将[B->·γ,b]加入到闭包中（B->γ是一个产生式）
                            List<String> remainingSymbolsAndProspect = new ArrayList<>(item.production.right.subList(item.dotPosition+1, item.production.right.size()));
                            remainingSymbolsAndProspect.add(item.prospect);
                            for (String prospect : computeRemainingSymbolsFirstSet(remainingSymbolsAndProspect, firstSets)){  //计算其右边符号串的first集
                                if (terminals.contains(prospect) || prospect.equals("#")) { // 展望符是#或者终结符
                                    LR1Item newItem = new LR1Item(production, 0, prospect);
                                    if (closure.add(newItem)) {  //加入闭包
                                        added = true;
                                    }
                                }
                            }

                        }
                    }
                }
            }
        } while (added);  //直到某次循环中没有加入新的项目
        return closure;
    }

    // 根据符号进行状态转移
    private static int findGoto(Set<LR1Item> itemSet, String symbol, List<Set<LR1Item>> itemSets) {  //从全部的项目集族中根据这个符号找到下一个项目集
        Set<LR1Item> gotoSet = new LinkedHashSet<>();
        for (LR1Item item : itemSet) {//如果点的位置不在最右端并且点的后面对应的符号就是这个符号，就把这个项目加入进来
            if (item.dotPosition < item.production.right.size() && item.production.right.get(item.dotPosition).equals(symbol)) {
                gotoSet.add(new LR1Item(item.production, item.dotPosition + 1, item.prospect));
            }
        }
        gotoSet = closure(gotoSet);  //计算闭包，完成项目集族的扩充

        if (!itemSets.contains(gotoSet)) {  //如果总的项目集族中没有这个项目集族就加入
            itemSets.add(gotoSet);
        }

        return itemSets.indexOf(gotoSet); //返回这个下标，即其对应的状态
    }

    // 输出Action表
    private static void printTable1(List<Map<String, String>> table) { //打印action表
        System.out.print(String.format("%-5s", ""));
        for (String terminal : terminals) {
            System.out.print(String.format("%-5s", terminal));
        }
        System.out.println();

        for (int i = 0; i < table.size(); i++) {
            System.out.print(String.format("%-5d", i));
            Map<String, String> row = table.get(i);
            for (String terminal : terminals) {
                System.out.print(String.format("%-5s", row.getOrDefault(terminal, "")));
            }
            System.out.println();
        }
    }

    // 输出Goto表
    private static void printTable2(List<Map<String, Integer>> table) { //打印goto表
        System.out.print(String.format("%-5s", ""));
        for (String nonTerminal : nonTerminals) {
            if(!nonTerminal.equals("S'"))
                System.out.print(String.format("%-5s", nonTerminal));
        }
        System.out.println();

        for (int i = 0; i < table.size(); i++) {
            System.out.print(String.format("%-5d", i));
            Map<String, Integer> row = table.get(i);
            for (String nonTerminal : nonTerminals) {
                if(!nonTerminal.equals("S'")) {
                    String s = String.valueOf(row.getOrDefault(nonTerminal, 0));
                    if (s.equals("0")) s = "";
                    System.out.print(String.format("%-5s", s));
                }
            }
            System.out.println();
        }
    }

    // 计算First集合
    private static Map<String, Set<String>> computeFirst() {
        Map<String, Set<String>> firstSets = new LinkedHashMap<>();
        firstSets.put("#", new HashSet<>(Collections.singletonList("#"))); // #的FIRST！
        // 初始化终结符的First集合
        for (String terminal : terminals) {
            firstSets.put(terminal, new HashSet<>(Collections.singletonList(terminal)));
        }

        // 初始化非终结符的First集合
        for (String nonTerminal : nonTerminals) {
            firstSets.put(nonTerminal, new HashSet<>());
        }

        boolean changed;
        do {
            changed = false;
            for (Production production : productions) {
                String left = production.left;
                List<String> right = production.right;
                int i = 0;
                while (i < right.size()) {
                    String symbol = right.get(i);
                    if (terminals.contains(symbol)) {
                        // 如果符号是终结符，将其添加到非终结符的First集合
                        if (firstSets.get(left).add(symbol)) {
                            changed = true;
                        }
                        break;
                    } else if (nonTerminals.contains(symbol)) {
                        // 如果符号是非终结符
                        Set<String> symbolFirstSet = firstSets.get(symbol);
                        if (symbolFirstSet.contains("$")) {    // 将符号的First集合（除了$）添加到非终结符的First集合中
                            Set<String> symbolFirstSetWithoutEpsilon = new LinkedHashSet<>();
                            symbolFirstSetWithoutEpsilon.addAll(symbolFirstSet);
                            symbolFirstSetWithoutEpsilon.remove("$");
                            if (firstSets.get(left).addAll(symbolFirstSetWithoutEpsilon)) {
                                changed = true;
                            }
                            i++;
                        } else if(!symbolFirstSet.contains("$")) {  //没有$就可以加完然后退出循环了
                            if (firstSets.get(left).addAll(symbolFirstSet)) {
                                changed = true;
                            }
                            break;
                        }
                    }
                }
                // 如果右侧所有符号都能推导出$，将$添加到非终结符的First集合中
                if (i == right.size()) {
                    if (firstSets.get(left).add("$")) {
                        changed = true;
                    }
                }
            }
        } while (changed);
        return firstSets;
    }

    // 计算Follow集合
    private static Map<String, Set<String>> computeFollow(Map<String, Set<String>> firstSets) {
        Map<String, Set<String>> followSets = new LinkedHashMap<>();
        // 初始化Follow集合
        for (String nonTerminal : nonTerminals) {
            followSets.put(nonTerminal, new HashSet<>());
        }
        String start=productions.get(0).left;
        // 将'#'（输入结束符）添加到开始符号的Follow集合中
        followSets.get(start).add("#");
        boolean changed;
        do {
            changed = false;
            for (Production production : productions) {
                String left = production.left;
                List<String> right = production.right;
                for (int i = 0; i < right.size(); i++) {
                    String symbol = right.get(i);  //右边的后续符号
                    if (nonTerminals.contains(symbol)) {
                        Set<String> symbolFollowSet = followSets.get(symbol);
                        if(i== right.size()-1){  //当前符号的后面没有符号了，就把左边符号的follow集加进去
                            if (symbolFollowSet.addAll(followSets.get(left))) {
                                changed = true;
                            }
                            break;
                        }
                        Set<String> remainingSymbolsFirstSet = computeRemainingSymbolsFirstSet(right.subList(i + 1, right.size()), firstSets); //计算右边符号串的first集
                        if (remainingSymbolsFirstSet.contains("$")) {
                            // 如果是最后一个符号或者剩余符号能推导出$，将左部符号的Follow集合添加到符号的Follow集合中
                            if (symbolFollowSet.addAll(followSets.get(left))) {
                                changed = true;
                            }
                        }
                        Set<String> remainingSymbolsFirstSetWithoutEpsilon=new HashSet<>(); //如果不能推出就把符号串的first集去掉$加进去
                        remainingSymbolsFirstSetWithoutEpsilon.addAll(remainingSymbolsFirstSet);
                        remainingSymbolsFirstSetWithoutEpsilon.remove("$");
                        if (symbolFollowSet.addAll(remainingSymbolsFirstSetWithoutEpsilon)) {
                            changed = true;
                        }
                    }
                }
            }
        } while (changed);
        return followSets;
    }

    // 计算剩余符号即符号串的First集合
    private static Set<String> computeRemainingSymbolsFirstSet(List<String> remainingSymbols, Map<String, Set<String>> firstSets) {
        Set<String> remainingSymbolsFirstSet = new HashSet<>();
        Set<String> symbolFirstSetWithoutEpsilon = new LinkedHashSet<>();  //不包含epsilon的first集合
        symbolFirstSetWithoutEpsilon.addAll(firstSets.get(remainingSymbols.get(0)));  //先加入第一个字符的first集
        symbolFirstSetWithoutEpsilon.remove("$");  //无论是否有都去掉
        remainingSymbolsFirstSet.addAll(symbolFirstSetWithoutEpsilon);  //再把没有epsilon的加入first集
        boolean allNonTerminalsProduceEpsilon = true;
        for (String symbol : remainingSymbols) {
            Set<String> symbolFirstSet = firstSets.get(symbol);
            if(symbolFirstSet.contains("$")){ // 将符号的 First 集合中除去 $（如果存在）的所有符号添加到符号串的 First 集合中
                remainingSymbolsFirstSet.addAll(symbolFirstSet);
                remainingSymbolsFirstSet.remove("$");
            }
            else if (!symbolFirstSet.contains("$")) { // 如果符号的 First 集合不包含 $，则不再继续向后添加
                remainingSymbolsFirstSet.addAll(symbolFirstSet);
                allNonTerminalsProduceEpsilon = false;
                break;
            }
        }
        if (allNonTerminalsProduceEpsilon) {
            // 如果符号串中的所有符号的 First 集合都包含 $，则将 $ 添加到符号串的 First 集合中
            remainingSymbolsFirstSet.add("$");
        }
        return remainingSymbolsFirstSet;
    }
}
